package struct.string;

import com.google.common.collect.Lists;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author: kanggw
 * @date: 2022/3/11
 * @DESCRIPTION:　给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 * 示例 1：
 *
 * 输入：s = "aab"
 * 输出：[["a","a","b"],["aa","b"]]
 * 示例 2：
 *
 * 输入：s = "a"
 * 输出：[["a"]]
 * https://leetcode-cn.com/problems/palindrome-partitioning/
 */
public class PalindromeSplit {

    static List<List<String>> result = Lists.newArrayList();
    static Deque<String> deque = new LinkedList<>();


    public static void main(String[] args) {

        split("a");
        result.forEach(item -> {
            item.forEach(i -> {

                System.out.print(i+",");
            });
            System.out.println();
        });


    }

    public static List<List<String>> split(String str) {

        backUp(str,0);

        return result;
    }

    public static void   backUp(String str,int startIndex) {

        //结束条件
        if(startIndex >= str.length()) {
            result.add(new ArrayList<>(deque));
            return;
        }

        for (int i = startIndex; i < str.length(); i++) {
            if (isHuiwen(str, startIndex, i )) {
                deque.addLast(str.substring(startIndex, i + 1));
                backUp(str, startIndex + 1);
                deque.removeLast();
            }
        }


    }


    public static boolean isHuiwen(String str,int left,int right) {

        while (left < right) {
            if (str.charAt(left++) != str.charAt(right--)) {
                return false;
            }
        }

        return true;
    }


}
